package com.atguigu.tree;

/**

 * @author 龍
 * 练习题：
 * 如果删除的节点是非叶子节点，现在不希望将该叶子节点的子树删除，需按照指定的规则，加入规定如下：
 * 1）该叶子节点只含有一个叶子节点b，将b代替a。
 * 2）存在两个子节点，让左子节点代替当前节点。
 */
public class BinaryTreeTest {
    public static void main(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
        HeroNode node1=new HeroNode(1,"宋江");
        HeroNode node2=new HeroNode(2,"吴用");
        HeroNode node3=new HeroNode(3,"卢俊义");
        HeroNode node4=new HeroNode(4,"林冲");
        HeroNode node5=new HeroNode(5,"关胜");
        //手动创建二叉树
        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        binaryTree.setRoot(node1);
        //开始进行遍历
        System.out.println("----------前序遍历-----------");
        binaryTree.preOrder();    //---1-2-3-4
        System.out.println("----------中序遍历-----------");
        binaryTree.infixOrder();  //---2-1-3-4
        System.out.println("----------后序遍历-----------");
        binaryTree.postOrder();  //---2-4-3-1
        node3.setLeft(node5);
        //开始进行遍历
        System.out.println("----------前序遍历-----------");
        binaryTree.preOrder();    //---1-2-3-5-4
        System.out.println("----------中序遍历-----------");
        binaryTree.infixOrder();  //---2-1-5-3-4
        System.out.println("----------后序遍历-----------");
        binaryTree.postOrder();  //---2-5-4-3-1
        System.out.println("***********前序遍历查找************");
        HeroNode resNode=binaryTree.preOrderSearch(5);
        if (resNode!=null){
            System.out.println("找到了，信息为："+resNode.toString());
        }else {
            System.out.println("未找到！！！");
        }
        System.out.println("***********中序遍历查找************");
        HeroNode resNode2=binaryTree.infixOrderSearch(5);
        if (resNode2!=null){
            System.out.println("找到了，信息为："+resNode2.toString());
        }else {
            System.out.println("未找到！！！");
        }
        System.out.println("***********后序遍历查找************");
        HeroNode resNode3=binaryTree.postOrderSearch(5);
        if (resNode3!=null){
            System.out.println("找到了，信息为："+resNode3.toString());
        }else {
            System.out.println("未找到！！！");
        }
        System.out.println("*************测试删除节点的操作************");
        System.out.println("删除前，前序遍历");
        binaryTree.preOrder();   //1-2-3-5-4
        binaryTree.delNode(5);
        System.out.println("删除后，前序遍历");
        binaryTree.preOrder();   //1-2-3-4



    }
}
/**
 * 定义BinaryTree
 */
class BinaryTree{
    private HeroNode root;
    public void setRoot(HeroNode root){
        this.root=root;
    }
    /**
     * 删除的节点:
     * 1)先判断root节点是不是所需要删除的节点，是的话直接删除
     * 2）不是的话进入递归删除
     */
    public void delNode(int no){
        if (root!=null){
            //直接进行判断root是不是要删除的节点
            if(root.getNo()==no){
                root=null;
            }else {
                root.delNode(no);
            }

        }else {
            System.out.println("空树，不能进行删除！！！");
        }
    }
    /**
     * 前序遍历
     */
    public void preOrder(){
        if (this.root!=null){
            this.root.preOrder();
        }else {
            System.out.println("当前二叉树为空，无法进行遍历！！！");
        }
    }
    /**
     * 中序遍历
     */
    public void infixOrder(){
        if (this.root!=null){
            this.root.infixOrder();
        }else {
            System.out.println("当前二叉树为空，无法进行遍历！！！");
        }
    }
    /**
     * 后序遍历
     */
    public void postOrder(){
        if (this.root!=null){
            this.root.postOrder();
        }else {
            System.out.println("当前二叉树为空，无法进行遍历！！！");
        }
    }
    /**
     * 前序遍历查找
     */
    public HeroNode preOrderSearch(int no){
        if (root!=null){
            return root.preOrderSearch(no);
        }else {
            return null;
        }
    }
    /**
     * 中序遍历查找
     */
    public HeroNode infixOrderSearch(int no){
        if (root!=null){
            return root.infixOrderSearch(no);
        }else {
            return null;
        }
    }
    /**
     * 后序遍历查找
     */
    public HeroNode postOrderSearch(int no){
        if (root!=null){
            return root.postOrderSearch(no);
        }else {
            return null;
        }
    }

}
/**
 * 先创建HeroNode节点
 */
class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;
    public HeroNode(int no,String name){
        this.no=no;
        this.name=name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
    /**
     * 递归删除节点
     * 规定：
     * 1）如果是叶子节点删除该节点。
     * 2）如果删除的节点是非叶子节点，则删除该子树。
     */
    public void delNode(int no){
        if (this.left!=null&&this.left.no==no){
            this.left=null;
            return;
        }
        if (this.right!=null&&this.right.no==no){
            this.right=null;
            return;
        }
        //想左子树进行递归删除
        if (this.left!=null){
            this.left.delNode(no);
        }
        //向右子树递归进行删除
        if (this.right!=null){
            this.right.delNode(no);
        }




    }
    /**
     * 编写前序遍历的方法
     */
    public void preOrder(){
        //先输出当前节点
        System.out.println(this);
        //向左子树前序遍历
        if (this.left!=null){
            this.left.preOrder();
        }
        if (this.right!=null){
            this.right.preOrder();
        }
    }
    /**
     * 中序遍历
     */
    public void infixOrder(){
        if (this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right!=null){
            this.right.infixOrder();
        }
    }
    /**
     * 后序遍历
     */
    public void postOrder(){
        if (this.left!=null){
            this.left.postOrder();
        }
        if (this.right!=null){
            this.right.postOrder();
        }
        System.out.println(this);
    }
    /**
     * 前序遍历查找
     */
    public HeroNode preOrderSearch(int no){
        System.out.println("开始进行比较=====");
        //先比较当前节点是不是
        if (this.no==no){
            return this;
        }
        HeroNode resNode=null;
        if (this.left!=null){
            resNode=this.left.preOrderSearch(no);
        }
        //说明左边找到了
        if (resNode!=null){
            return resNode;
        }
        if (this.right!=null){
           resNode= this.right.preOrderSearch(no);
        }
        //判断resNode来判断是否查找到了所需要的节点。
        return resNode;
    }
    /**
     * 中序遍历查找
     */
    public HeroNode infixOrderSearch(int no){
        HeroNode resNode=null;
        if (this.left!=null){
            resNode=this.left.infixOrderSearch(no);
        }
        if (resNode!=null){
            return resNode;
        }
        System.out.println("开始进行比较=====");
        if (this.no==no){
            return this;
        }
        if (this.right!=null){
            resNode=this.right.infixOrderSearch(no);
        }
        return resNode;
    }
    /**
     * 中序遍历查找
     */
    public HeroNode postOrderSearch(int no){
        HeroNode resNode=null;
        if (this.left!=null){
            resNode=this.left.postOrderSearch(no);
        }
        //说明在左子树找到了
        if (resNode!=null){
            return resNode;
        }

        if (this.right!=null){
            resNode=this.right.postOrderSearch(no);
        }
        if (resNode!=null){
            return resNode;
        }
        System.out.println("开始进行比较=====");
        if (this.no==no){
            return this;
        }
        return resNode;
    }
}

